package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1186 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 不是因为复杂，而是因为经典
     * 未来需要再次复习此道题目
     * 参考：https://leetcode-cn.com/problems/maximum-subarray-sum-with-one-deletion/solution/dian-xing-de-zhuang-tai-ji-dpwen-ti-by-y-q6mq/
     * 经典，我主要是状态转移想错了
     * @return:
     */
    class Solution {
        public int maximumSum(int[] nums) {
            //    nums[i] > 0 时，类似求连续数组和的最大值，看前一位的累加和是否大于0即可。小于0的话，从i重新计算；大于等于0的话可以和前面连在一起计算。但“已删除”必须由前面迭代而来，不然就空数组了，不符题意。
            //    nums[i] < 0 时，“未删除”状态，就还是从未删除状态转移过来、或只算当前位置。“已删除”状态可以是之前没删、这一位删了，或是之前就删了。所以取 未删除状态和已删除状态+nums[i]的最大值。
            // 初始化：dp0 表示未删除，和为nums[0]。dp1表示已删除，空数组，和为0。
            // 但 rs 初始化只能为dp0，而不是`Math.max(dp0, dp1)`。因为空数组不符合题意。
            // dp1 这个状态需要留着迭代，但不能作为返回值。
            int dp0 = nums[0], dp1 = 0, rs = dp0;
            for (int i = 1; i < nums.length; i++) {
                int num = nums[i];
                if (num >= 0) {
                    dp0 = Math.max(0, dp0) + num;
                    dp1 = dp1 + num; // 不能留空数组，所以不是 Math.max(0, dp1)
                } else {
                    dp1 = Math.max(dp0, dp1 + num); // 这一位删除，或以前已删除
                    // 这里dp0在下面，因为dp0的更新用不到dp1，不会因为刚更新的值覆盖了旧值导致错误。
                    dp0 = Math.max(0, dp0) + num;
                }
                // 更新最大值
                rs = Math.max(rs, dp0);
                rs = Math.max(rs, dp1);
            }
            return rs;
        }
    }


    class Solution_Wrong_Thought {
        public int maximumSum(int[] arr) {
            int ans = arr[0], i = 1, curCanDeleteSum = arr[0], prevMin = 0;
            while (i < arr.length) {
                if (curCanDeleteSum < 0) {
                    curCanDeleteSum = arr[i];
                    prevMin = 0;
                } else {
                    curCanDeleteSum += arr[i];
                    if (arr[i] < prevMin) {
                        curCanDeleteSum += (prevMin - arr[i]);
                        prevMin = arr[i];
                    }
                }

                ans = Math.max(ans, curCanDeleteSum);
                i++;
            }

            return ans;
        }
    }

    public void run() {
//        System.out.println(new Solution().maximumSum(InputUtil.toIntegerArray("[1,-2,0,3]")));
//        System.out.println(new Solution().maximumSum(InputUtil.toIntegerArray("[1,-2,-2,3]")));
//        System.out.println(new Solution().maximumSum(InputUtil.toIntegerArray("[-1,-1,-1,-1]")));
//        System.out.println(new Solution().maximumSum(InputUtil.toIntegerArray("[1,-4,-5,-2,5,0,-1,2]")));
        System.out.println(new Solution().maximumSum(InputUtil.toIntegerArray("[11,-10,-11,8,7,-6,9,4,11,6,5,0]")));
    }

    public static void main(String[] args) throws Exception {
        LC1186 an = new LC1186();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
